#include "Kruskal.h"

Kruskal::Kruskal(Solucao *sol){
         //Alloca um vetor com tamanho Arranjo de numSteiner dois a dois
	this->arvore = MAX_STEINER;
        int tamLigacao = (sol->tamanho * (sol->tamanho - 1) /2);
	int *c = new int[tamLigacao];
	int *s = new int[tamLigacao];
	double *cus = new double[tamLigacao];
        int n1, n2;
        n1 = n2 = 0;
	numAresta = sol->tamanho;
	int count = 0;
        for(int i=0; i < sol->tamanho; i++){
        	//vertices[i] = new NoVertice(i);
        	vertices[i].set(i);
                if(sol->solucao[i]){
                        for(int j=i+1; j < sol->tamanho; j++){
                                if(sol->solucao[j]){
					c[n2] = i;
					s[n2] = j;
					cus[n2] = sol->linkSteiner[n1];
                                        n2++;
                                }
                                n1++;
                        }
                }else{
                        n1 += (sol->tamanho - (i + 1));
                }
        }
	this->arestas = new ListaAresta(n2);
	this->arestas->insereOrdenado(c, s, cus);
}

int Kruskal::getArvore(int no){
	return this->vertices[no].arvore;
}

void Kruskal::uniao(int no1, int no2){
	if(vertices[no1].arvore >= MAX_STEINER){
		if(vertices[no2].arvore >= MAX_STEINER){
			int a = vertices[no2].arvore;
			for(int i=0; i<numAresta; i++){
				if(vertices[i].arvore == a)	
					vertices[i].arvore = vertices[no1].arvore;
			}
		}else{
			vertices[no2].arvore = vertices[no1].arvore;
		}
	}else{
		if(vertices[no2].arvore >= MAX_STEINER){
			vertices[no1].arvore = vertices[no2].arvore;	
		}else{
			vertices[no2].arvore = vertices[no1].arvore = this->arvore;
			this->arvore++;
		}
	}
}

double Kruskal::getSomaArestas(){
	double soma = 0;
	while(this->arestas->hasNext()){
		NoAresta *aux = this->arestas->getNext();
		if(this->getArvore(aux->no1) != this->getArvore(aux->no2)){
			//printf("A1: %d A2: %d\n", aux->no1, aux->no2);
			soma += aux->peso;
			this->uniao(aux->no1, aux->no2);
		}
		delete aux;
	}
	return soma;
}

//NoVertice Kruskal::vertices[MAX_STEINER];
